<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en-us">
<head>
  <title>
    计算两个平行于坐标轴的矩形相交的面积 // 飞狐的部落格
  </title>

  <link href="http://gmpg.org/xfn/11" rel="profile">
<meta http-equiv="content-type" content="text/html; charset=utf-8">


<meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1">

<meta name="description" content="检测矩形是否相交，检测矩形面积">
<meta name="keywords" content="算法,">
<meta name="author" content="飞狐">
<meta name="generator" content="Hugo 0.14" />

  <meta property="og:title" content="计算两个平行于坐标轴的矩形相交的面积" />
<meta property="og:description" content="检测矩形是否相交，检测矩形面积" />
<meta property="og:type" content="website" />
<meta property="og:locale" content="en_US" />
<meta property="og:url" content="http://lucumt.info/posts/calculate-total-area-of-two-rectangles/" />


  
   <link rel="stylesheet" href="http://lucumt.info/css/base-min.css">
   <link rel="stylesheet" href="http://lucumt.info/css/pure-min.css">
  
  
    <link rel="stylesheet" href="http://lucumt.info/css/grids-responsive-min.css">
  
  

  <link rel="stylesheet" href="http://lucumt.info/css/redlounge.css">
  
  <link rel="stylesheet" href="http://lucumt.info/css/googleapis.font.css">
  <link rel="stylesheet" href="http://lucumt.info/css/jqcloud.css">
  <link href="//maxcdn.bootstrapcdn.com/font-awesome/4.2.0/css/font-awesome.min.css" rel="stylesheet">
  

  
  <link rel="apple-touch-icon-precomposed" sizes="144x144" href="http://lucumt.info/touch-icon-144-precomposed.png">
  <link rel="shortcut icon" href="http://lucumt.info/lucumt.ico">

  
  <link href="" rel="alternate" type="application/rss+xml" title="飞狐的部落格" />

  <script src="http://lucumt.info//js/jquery.min.js"></script>
  <script src="http://lucumt.info//js/jqcloud-1.0.4.min.js"></script>

    
  
  <link rel="stylesheet" href="//cdnjs.cloudflare.com/ajax/libs/highlight.js/9.6.0/styles/rainbow.min.css">
  
  <script src="http://lucumt.info/js/highlight.min.js"></script>
  <script>hljs.initHighlightingOnLoad();</script>


  

  

  

<script>
  (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
  (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
  m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
  })(window,document,'script','//www.google-analytics.com/analytics.js','ga');

  ga('create', "UA-75123653-1", 'auto');
  ga('send', 'pageview');
</script>




<script>
var _hmt = _hmt || [];
(function() {
  var hm = document.createElement("script");
  hm.src = "https://hm.baidu.com/hm.js?cabc0a71f63da092412d82d1aefe7d1c";
  var s = document.getElementsByTagName("script")[0]; 
  s.parentNode.insertBefore(hm, s);
})();
</script>

</head>
<body>
	
		<div id="nav-to-top">
			<span class="decorative-marker">//</span><a href="#top">返回顶部</a>
		</div>
	

	<div id="layout" class="pure-g">
    
		 <a href="https://github.com/lucumt/ghblog" target="_new">
			<img style="position: absolute; top: 0; right: 0; border: 0;" 
			src="/img/forkme_right_red.png" alt="Fork me on GitHub">
		</a>

    <div class="sidebar pure-u-1 pure-u-md-1-4">
  <div class="header">
    

	
	  <img src="http://lucumt.info/img/photo.jpg" class="profilepic">
	

    <h1 class="brand-title">飞狐的部落格</h1>
    <h2 class="brand-tagline">Rosen Lu</h2>

    <nav class="nav">
      <ul class="nav-list">
        <li class="nav-item"><span class="nav-item-separator">//</span><a href="http://lucumt.info/">Home</a></li>
        
          <li class="nav-item"><span class="nav-item-separator">//</span><a href="http://lucumt.info/about/">About</a></li>
        
          <li class="nav-item"><span class="nav-item-separator">//</span><a href="http://lucumt.info/posts/">Blog</a></li>
        
      </ul>
    </nav>

    
    <div class="social-buttons">
      
        
        <a href="https://github.com/lucumt" target="_blank"><i class='fa fa-github'></i></a>
        
      
        
        <a href="https://plus.google.com/u/0/115794588502118898127/posts" target="_blank"><i class='fa fa-google-plus'></i></a>
        
      
        
        <a href="https://www.facebook.com/rosen.lu.1" target="_blank"><i class='fa fa-facebook'></i></a>
        
      
        
        <a href="http://www.twitter.com/rosenlucumt" target="_blank"><i class='fa fa-twitter'></i></a>
        
      
        
        <a href="mailto:lucumt@gmail.com" target="_blank"><i class='fa fa-mail-forward'></i></a>
        
      
    </div>
    
    
	
	  <hr class="nav-site-separator"/>
	  <nav class="nav">
      <ul class="nav-list">
	    
		   <li class="nav-site"><a href="http://lilydjwg.is-programmer.com/" target="_blank">依云的博客</a></li>
		
		   <li class="nav-site"><a href="http://evilbinary.org/" target="_blank">邪恶二进制</a></li>
		
		   <li class="nav-site"><a href="http://www.wlman.cc/" target="_blank">Consec &#39;s Blog</a></li>
		
		   <li class="nav-site"><a href="http://www.linuxzen.com/" target="_blank">cold&#39;s world</a></li>
		
		   <li class="nav-site"><a href="http://frantic1048.logdown.com/" target="_blank">Frantic log#1048</a></li>
		
	  </ul>
	  </nav>
	
	

  </div>
</div>

	
	

    <div class="content pure-u-1 pure-u-md-3-4">
		<a name="top"></a>
		

		
			
	    
  		<section class="post">
            <h1 class="post-title">
              <a href="http://lucumt.info/posts/calculate-total-area-of-two-rectangles">计算两个平行于坐标轴的矩形相交的面积</a>
            </h1>
            <h3 class="post-subtitle">
            	
            </h3>
            
            	<span class="post-date">
                	<span class="post-date-day"><sup>26</sup></span><span class="post-date-separator">/</span><span class="post-date-month">Feb</span> <span class="post-date-year">2017</span>
            	</span>
            	
            
            	
            		<span class="post-author-single">By <a class="post-author" href="https://www.linkedin.com/in/%E8%BF%90%E5%BC%BA-%E5%8D%A2-50a08bb5/" target="_new">飞狐</a></span>
            		




            	
            

			
			
				<div class="post-categories">
				
					<a class="post-category post-category-%E7%AE%97%E6%B3%95" href="http://lucumt.info//categories/%E7%AE%97%E6%B3%95">算法</a>
				
				</div>
			

			

			

            <p>之前面试时遇到一个算法题: <strong>假定两个矩形各条边都是平行于坐标轴，已知k、l、m、n分别为其中一个矩形左下角和右上角x轴、y轴坐标，p、q、r、s分别为另一个矩形的左下角和右上角x轴、y轴坐标，求这两个矩形的总面积，当矩形相交时要减去相交的面积。</strong> 此题利用常规的枚举法很复杂，但利用排除法和归纳法却能很快解决，故先记录下。</p>

<p>很明显，此题的重点在于如何判断矩形是否相交以及检测相交形成的新矩形面积，当不相交时总面积直接为两个矩形的面积之和，当相交时需要减去相交矩形的面积，由于题目已经告诉了矩形的左下角和右上角坐标已知，问题又转化为在相交时如何计算相交矩形的左下角和右上角的坐标。</p>

<p>最开始我想通过常规的枚举法把矩形相交的所有情况都列出来，在稿纸上简单的比划后，发现采用枚举的方式太复杂，矩形相交理论上有下图所示的16种组合方式，短时间内很难一一列举出来，实际编程中不仅代码量大还很容易产生遗漏。<br />
<img src="http://lucumt.info/blog_img/calculate-total-area-of-two-rectangles/intersect1.png" alt="矩形相交1" title="两个矩形边角相交以及完全包含" />

<img src="http://lucumt.info/blog_img/calculate-total-area-of-two-rectangles/intersect2.png" alt="矩形相交2" title="矩形横向相交" />
<br />
<img src="http://lucumt.info/blog_img/calculate-total-area-of-two-rectangles/intersect3.png" alt="矩形相交3" title="矩形纵向相交" />

<img src="http://lucumt.info/blog_img/calculate-total-area-of-two-rectangles/intersect4.png" alt="矩形相交4" title="矩形被完全包含" />
<br />
排除枚举方法之后，只能对其进行分析找出通用的处理方式。下图展示了在相交矩形的左下角和右上角的位置，仔细分析后便可发现<strong>相交矩形的左下角x,y坐标是两个矩形左下角x,y坐标中取较大值，相交矩形的右上角x,y坐标是两个矩形右上角x,y坐标中取较小值</strong>。<br />
<img src="http://lucumt.info/blog_img/calculate-total-area-of-two-rectangles/position_calculate.png" alt="矩形相交坐标计算" title="矩形相交时形成的新矩形的坐标来源" />
<br />
通过分析归纳之后，我们将之前的16种相交情况统一为1个表达式，而这个表达式在编程时是很容易实现的，下面的代码展示了如何利用该表达式计算相交矩形的坐标以及其面积。</p>

<pre><code class="language-java">public static int calculateIntersectArea(int k, int l, int m, int n, int p,int q, int r, int s) {
	int leftDownX = 0, leftDownY = 0, rightUpX = 0, rightUpY = 0;
	leftDownX = k &gt; p ? k : p;
	leftDownY = l &gt; q ? l : q;
	rightUpX = m &lt; r ? m : r;
	rightUpY = n &lt; s ? n : s;
	return (rightUpX - leftDownX) * (rightUpY - leftDownY);
}
</code></pre>

<p>寻找出如何计算相交矩形的面积之后，还需要解决一个问题:<strong>上述实现只有在矩形相交时才正确，当矩形不相交时计算结果错误</strong>，为此需要找出一个方法判定两个矩形是否相交。若利用枚举方法同样会有前述的16种情形需要考虑，同样很复杂，显然枚举方法不适合使用。换一种思路：<strong>如果把矩形不相交的情形排除掉，那么剩下的情形就是矩形相交了！</strong>，而矩形不相交则相对容易多了，假设这两个矩形分别为A和B，则它们不相交一共有如下图所示的4种情况：<br />
<img src="http://lucumt.info/blog_img/calculate-total-area-of-two-rectangles/no_interact_position_compare.png" alt="矩形不相交坐标计算" title="矩形不相交的4种情况" />
<br />
相应的代码实现如下：</p>

<pre><code class="language-java">public static boolean isIntersect(int k, int l, int m, int n, int p, int q, int r, int s) {
	
	boolean nointersect = false;
	// B在A的上面
	nointersect = q &gt; n;
	// B在A的下面
	nointersect = l &gt; s;
	// B在A的左侧
	nointersect = r &lt; k;
	// B在A的右侧
	nointersect = m &lt; p;

	return !nointersect;
}
</code></pre>

<p>利用上述2个判断方法，可以方便准确的计算出两个矩形在相交时的总面积，相应的代码如下:</p>

<pre><code class="language-java">public static int solution(int k, int l, int m, int n, int p, int q, int r, int s) {

	int widthA = m - k;
	int heightA = n - l;
	int areaA = widthA * heightA;

	int widthB = r - p;
	int heightB = s - q;
	int areaB = widthB * heightB;
	int totalArea = areaA + areaB;

	boolean hasIntersect = isIntersect(k, l, m, n, p, q, r, s);
	if (hasIntersect) {
		totalArea -= calculateIntersectArea(k, l, m, n, p, q, r, s);
	}
	return totalArea;
}
</code></pre>

<p>分析解决这个问题给我最深的感触是：<strong>有时候若某一类问题用枚举实现很复杂时，尝试去分析其中的规律，找出通用的解决方法</strong>，不仅在算法方面，或许在生活中其它方面也适用吧！</p>

	
			

			

			
          </section>
		  
		  <div class="page-link">
			
			<a href="http://lucumt.info/posts/show-video-in-html5-page/">//下一篇</a>
			
			&nbsp;
			
			<a class="page-link-right" href="http://lucumt.info/posts/import-local-package-in-intellij-idea/">//上一篇</a>
			
	      </div>

          
          	<div id="disqus_thread"></div>
<script type="text/javascript">
    var disqus_shortname = 'rosenlu';
    var disqus_identifier = 'http:\/\/lucumt.info\/posts\/calculate-total-area-of-two-rectangles\/';
    var disqus_title = '计算两个平行于坐标轴的矩形相交的面积';
    var disqus_url = 'http:\/\/lucumt.info\/posts\/calculate-total-area-of-two-rectangles\/';

    (function() {
        var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true;
        dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js';
        (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
    })();
</script>
<noscript>Please enable JavaScript to view the <a href="http://disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
<a href="http://disqus.com" class="dsq-brlink">comments powered by <span class="logo-disqus">Disqus</span></a>
          
        
      <div class="footer">
	<hr class="thin" />
	<div class="pure-menu pure-menu-horizontal pure-menu-open">
		<ul class="footer-menu">
		
			<li><a href="https://github.com/tmaiaroto/hugo-redlounge">Designed by Red Lounge</a></li>
		
		</ul>
	</div>

	<p>&copy; 2017. All rights reserved.</p>
</div>
    </div>
  </div>
	
		<script type="text/javascript">
			onscroll = function() {
			  var toTopVisible = false;
			  var scrollTop = document.documentElement.scrollTop || document.body.scrollTop;
			  if (scrollTop > 1000) {
			    if (!toTopVisible) {
			      document.getElementById('nav-to-top').style.display = 'block';
			    }
			  } else {
			    if (scrollTop < 1000 || toTopVisible) {
			      document.getElementById('nav-to-top').style.display = 'none';
			    }
			  }
			};
		</script>
	

	

  
</body>
</html>